"""
冒泡排序：
    概述：
        相邻元素两两比较，大的数据往后走，这样第一轮比较完毕后，最大的元素就会被交换到最后面。
    过程：
        1. 比较相邻的两个元素，如果第一个比第二个大，就交换他们的位置。
        2. 对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对，最后的元素会是最大的数。
        3. 针对所有的元素重复以上的步骤，除了最后一个。
        4. 重复以上的步骤，直到没有任何一对数字需要比较。
    时间复杂度：
        最优时间复杂度：O(N)
        最坏时间复杂度：O(N^2)
    空间复杂度：O(1)
    稳定性：稳定
    核心：
        1：比较的总轮数：   列表的长度-1
        2：每轮比较的次数： 列表的长度-1-当前的轮数（从0开始计数）
        3：谁和谁比较：    my_list[j]和my_list[j+1]
        4：如果前者大于后者，就交换他们的位置。
"""
# 1: 定义函数bubble_sort(my_list)
def bubble_sort(my_list):
    # 1.1：获取列表的长度
    n = len(my_list)
    # 1.2：外层循环，比较的总轮数
    for i in range(n-1):
        # 定义变量，记录每轮交换的次数。
        count = 0
        # 1.3: 内层循环，每轮比较的次数
        for j in range(n-1-i):
            # 1.4：谁和谁比较：    my_list[j]和my_list[j+1]
            if my_list[j] > my_list[j+1]:
                # 1.5: 如果 前面的元素比后面的元素大，则交换位置
                my_list[j], my_list[j+1] = my_list[j+1], my_list[j]
                # 1.6: 记录交换的次数
                count += 1

        if count == 0:
            # 1.7: 如果没有交换，则提前结束
            break

        print(f"交换了{count}次")

if __name__ == '__main__':
    my_list = [5, 4, 1, 2, 3]
    print("排序前：", my_list)
    bubble_sort(my_list)
    print("排序后：", my_list)
